{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Contain Virus"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #breadth-first-search #array #matrix #simulation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #广度优先搜索 #数组 #矩阵 #模拟"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: containVirus"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #隔离病毒"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>病毒扩散得很快，现在你的任务是尽可能地通过安装防火墙来隔离病毒。</p>\n",
    "\n",
    "<p>假设世界由&nbsp;<code>m x n</code>&nbsp;的二维矩阵&nbsp;<code>isInfected</code>&nbsp;组成，&nbsp;<code>isInfected[i][j] == 0</code>&nbsp;表示该区域未感染病毒，而 &nbsp;<code>isInfected[i][j] == 1</code>&nbsp;表示该区域已感染病毒。可以在任意 2 个相邻单元之间的共享边界上安装一个防火墙（并且只有一个防火墙）。</p>\n",
    "\n",
    "<p>每天晚上，病毒会从被感染区域向相邻未感染区域扩散，除非被防火墙隔离。现由于资源有限，每天你只能安装一系列防火墙来隔离其中一个被病毒感染的区域（一个区域或连续的一片区域），且该感染区域对未感染区域的威胁最大且 <strong>保证唯一&nbsp;</strong>。</p>\n",
    "\n",
    "<p>你需要努力使得最后有部分区域不被病毒感染，如果可以成功，那么返回需要使用的防火墙个数; 如果无法实现，则返回在世界被病毒全部感染时已安装的防火墙个数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2021/06/01/virus11-grid.jpg\" style=\"height: 255px; width: 500px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> isInfected = [[0,1,0,0,0,0,0,1],[0,1,0,0,0,0,0,1],[0,0,0,0,0,0,0,1],[0,0,0,0,0,0,0,0]]\n",
    "<strong>输出:</strong> 10\n",
    "<strong>解释:</strong>一共有两块被病毒感染的区域。\n",
    "在第一天，添加 5 墙隔离病毒区域的左侧。病毒传播后的状态是:\n",
    "<img src=\"https://assets.leetcode.com/uploads/2021/06/01/virus12edited-grid.jpg\" style=\"height: 261px; width: 500px;\" />\n",
    "第二天，在右侧添加 5 个墙来隔离病毒区域。此时病毒已经被完全控制住了。\n",
    "<img src=\"https://assets.leetcode.com/uploads/2021/06/01/virus13edited-grid.jpg\" style=\"height: 261px; width: 500px;\" />\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2021/06/01/virus2-grid.jpg\" style=\"height: 253px; width: 653px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> isInfected = [[1,1,1],[1,0,1],[1,1,1]]\n",
    "<strong>输出:</strong> 4\n",
    "<strong>解释:</strong> 虽然只保存了一个小区域，但却有四面墙。\n",
    "注意，防火墙只建立在两个不同区域的共享边界上。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例&nbsp;3:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> isInfected = [[1,1,1,0,0,0,0,0,0],[1,0,1,0,1,1,1,1,1],[1,1,1,0,0,0,0,0,0]]\n",
    "<strong>输出:</strong> 13\n",
    "<strong>解释:</strong> 在隔离右边感染区域后，隔离左边病毒区域只需要 2 个防火墙。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m ==&nbsp;isInfected.length</code></li>\n",
    "\t<li><code>n ==&nbsp;isInfected[i].length</code></li>\n",
    "\t<li><code>1 &lt;= m, n &lt;= 50</code></li>\n",
    "\t<li><code>isInfected[i][j]</code>&nbsp;is either&nbsp;<code>0</code>&nbsp;or&nbsp;<code>1</code></li>\n",
    "\t<li>在整个描述的过程中，总有一个相邻的病毒区域，它将在下一轮 <strong>严格地感染更多未受污染的方块</strong>&nbsp;</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [contain-virus](https://leetcode.cn/problems/contain-virus/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [contain-virus](https://leetcode.cn/problems/contain-virus/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[0,1,0,0,0,0,0,1],[0,1,0,0,0,0,0,1],[0,0,0,0,0,0,0,1],[0,0,0,0,0,0,0,0]]', '[[1,1,1],[1,0,1],[1,1,1]]', '[[1,1,1,0,0,0,0,0,0],[1,0,1,0,1,1,1,1,1],[1,1,1,0,0,0,0,0,0]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containVirus(self, A: List[List[int]]) -> int:\n",
    "        m, n = len(A), len(A[0])\n",
    "\n",
    "        def spread(x):\n",
    "            for uninfect in x:\n",
    "                for a, b in uninfect:\n",
    "                    A[a][b] = 1\n",
    "\n",
    "        def get_region():\n",
    "            areas = []\n",
    "            walls = []\n",
    "            uninfects = []\n",
    "            vis = set()\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if A[i][j] == 1 and (i, j) not in vis:\n",
    "                        area, wall, uninfect = [(i, j)], 0, set()\n",
    "                        vis.add((i, j))\n",
    "                        q = deque([(i, j)])\n",
    "                        while q:\n",
    "                            cx, cy = q.popleft()\n",
    "                            for dx, dy in [(0, -1), (0, 1), (1, 0), (-1, 0)]:\n",
    "                                nx, ny = cx + dx, cy + dy\n",
    "                                if 0 <= nx < m and 0 <= ny < n:\n",
    "                                    if A[nx][ny] == 1:\n",
    "                                        if (nx, ny) in vis: continue\n",
    "                                        vis.add((nx, ny))\n",
    "                                        area.append((nx, ny))\n",
    "                                        q.append((nx, ny))\n",
    "                                    elif A[nx][ny] == 0:\n",
    "                                        wall += 1\n",
    "                                        uninfect.add((nx, ny))\n",
    "                        areas.append(area)\n",
    "                        walls.append(wall)\n",
    "                        uninfects.append(uninfect)\n",
    "            return areas, walls, uninfects\n",
    "\n",
    "\n",
    "        areas, walls, uninfects = get_region()\n",
    "        ans = 0\n",
    "        while areas:\n",
    "            num_areas = len(areas)\n",
    "            if sum(map(len, areas)) == m * n:\n",
    "                return ans\n",
    "            idx = 0\n",
    "            for i in range(num_areas):\n",
    "                if len(uninfects[i]) > len(uninfects[idx]):\n",
    "                    idx = i\n",
    "            ans += walls[idx]\n",
    "            for a, b in areas[idx]:\n",
    "                A[a][b] = -1\n",
    "            spread(uninfects[:idx] + uninfects[idx+1:])\n",
    "            areas, walls, uninfects = get_region()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containVirus(self, isInfected: List[List[int]]) -> int:\n",
    "        dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]\n",
    "        \n",
    "        m, n = len(isInfected), len(isInfected[0])\n",
    "        ans = 0\n",
    "\n",
    "        while True:\n",
    "            neighbors, firewalls = list(), list()\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if isInfected[i][j] == 1:\n",
    "                        q = deque([(i, j)])\n",
    "                        neighbor = set()\n",
    "                        firewall, idx = 0, len(neighbors) + 1                        \n",
    "\n",
    "                        while q:\n",
    "                            x, y = q.popleft()\n",
    "                            if isInfected[x][y]<0:continue\n",
    "                            isInfected[x][y]=-idx\n",
    "                            for dx,dy in dirs:\n",
    "                                nx, ny = x + dx, y + dy\n",
    "                                if 0 <= nx < m and 0 <= ny < n:\n",
    "                                    if isInfected[nx][ny] == 1:\n",
    "                                        q.append((nx, ny))\n",
    "                                    elif isInfected[nx][ny] == 0:\n",
    "                                        firewall += 1\n",
    "                                        neighbor.add((nx, ny))\n",
    "                        \n",
    "                        neighbors.append(neighbor)\n",
    "                        firewalls.append(firewall)\n",
    "            \n",
    "            if not neighbors:\n",
    "                break\n",
    "\n",
    "            idx = 0\n",
    "            for i in range(len(neighbors)):\n",
    "                if len(neighbors[i]) > len(neighbors[idx]):\n",
    "                    idx = i\n",
    "                \n",
    "            ans += firewalls[idx]\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if isInfected[i][j] < 0:\n",
    "                        if isInfected[i][j] != -idx - 1:\n",
    "                            isInfected[i][j] = 1\n",
    "                        else:\n",
    "                            isInfected[i][j] = 2\n",
    "            \n",
    "            for i, neighbor in enumerate(neighbors):\n",
    "                if i == idx:continue\n",
    "                for x, y in neighbor:\n",
    "                    isInfected[x][y] = 1\n",
    "            \n",
    "            # if len(neighbors) == 1:\n",
    "            #     break\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containVirus(self, isInfected: List[List[int]]) -> int:\n",
    "        m, n = len(isInfected), len(isInfected[0])\n",
    "        directions = [(0,1),(0,-1),(1,0),(-1,0)]\n",
    "\n",
    "        def bfs1(i,j):  # return number of cells that can be infected\n",
    "            cells = set()\n",
    "            q = deque([(i,j)])\n",
    "            visited[i][j] = 1\n",
    "            while q:\n",
    "                i,j = q.popleft()\n",
    "                for di,dj in directions:\n",
    "                    a, b = i+di, j+dj\n",
    "                    if a < 0 or a >= m or b < 0 or b >= n or visited[a][b] or isInfected[a][b] == -1:\n",
    "                        continue\n",
    "                    if isInfected[a][b] == 1:\n",
    "                        q.append((a,b))\n",
    "                        visited[a][b] = 1\n",
    "                    else:\n",
    "                        cells.add((a,b))\n",
    "            return len(cells)\n",
    "\n",
    "        def bfs2(i,j):  # quarantine current block and return number of walls used\n",
    "            ans = 0\n",
    "            q = deque([(i,j)])\n",
    "            isInfected[i][j] = -1\n",
    "            while q:\n",
    "                i,j = q.popleft()\n",
    "                for di,dj in directions:\n",
    "                    a, b = i+di, j+dj\n",
    "                    if a < 0 or a >= m or b < 0 or b >= n or isInfected[a][b] == -1:\n",
    "                        continue\n",
    "                    if isInfected[a][b] == 1:\n",
    "                        q.append((a,b))\n",
    "                        isInfected[a][b] = -1\n",
    "                    else:\n",
    "                        ans += 1\n",
    "            return ans\n",
    "\n",
    "        def infect():\n",
    "            res = []\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if isInfected[i][j] != 0: continue\n",
    "                    for di,dj in directions:\n",
    "                        a, b = i+di, j+dj\n",
    "                        if 0 <= a < m and 0 <= b < n and isInfected[a][b] == 1:\n",
    "                            res.append((i,j))\n",
    "                            break\n",
    "            for i,j in res:\n",
    "                isInfected[i][j] = 1\n",
    "\n",
    "        ans = 0\n",
    "        while True:\n",
    "            visited = [[0]*n for _ in range(m)]\n",
    "            c = Counter()\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if isInfected[i][j] == 1 and visited[i][j] == 0:\n",
    "                        c[(i,j)] = bfs1(i,j)\n",
    "            if not c:\n",
    "                return ans\n",
    "            i0,j0 = c.most_common(1)[0][0]\n",
    "            ans += bfs2(i0,j0)\n",
    "            infect()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containVirus(self, isInfected: List[List[int]]) -> int:\n",
    "        m, n = len(isInfected), len(isInfected[0]) \n",
    "        ans = 0 \n",
    "        dx = [1, -1, 0, 0]\n",
    "        dy = [0, 0, 1, -1]\n",
    "        \n",
    "        while True:\n",
    "            neis, walls = list(), list() \n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if isInfected[i][j] == 1:\n",
    "                        Q = deque([(i,j)])\n",
    "                        wall, idx = 0, len(neis) + 1\n",
    "                        nei = set() \n",
    "                        isInfected[i][j] = -idx \n",
    "                        while Q:\n",
    "                            x, y = Q.popleft()\n",
    "                            \n",
    "                            for d in range(4):\n",
    "                                nx,ny = x+dx[d], y+dy[d]\n",
    "                                if 0<=nx<m and 0<=ny<n:\n",
    "                                    if isInfected[nx][ny] == 1:\n",
    "                                        Q.append((nx,ny))\n",
    "                                        isInfected[nx][ny] = -idx\n",
    "                                    elif isInfected[nx][ny] == 0:\n",
    "                                        nei.add((nx,ny))\n",
    "                                        wall += 1 \n",
    "                        neis.append(nei)\n",
    "                        walls.append(wall) \n",
    "            if not neis:\n",
    "                break \n",
    "            \n",
    "            idx = 0 \n",
    "            for i in range(1, len(neis)):\n",
    "                if len(neis[i]) > len(neis[idx]):\n",
    "                    idx = i \n",
    "            #print(neis, walls)\n",
    "            #print(idx) \n",
    "            ans += walls[idx]\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if isInfected[i][j] < 0:\n",
    "                        if isInfected[i][j] != -idx-1:\n",
    "                            isInfected[i][j] = 1 \n",
    "                        else:\n",
    "                            isInfected[i][j] = 2 \n",
    "            for i, nei in enumerate(neis):\n",
    "                if i != idx:\n",
    "                    for x, y in nei:\n",
    "                        isInfected[x][y] = 1 \n",
    "        return ans \n",
    "             \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\r\n",
    "import heapq\r\n",
    "class Solution:\r\n",
    "    def containVirus(self, isInfected: List[List[int]]) -> int:\r\n",
    "        R=len(isInfected)\r\n",
    "        C=len(isInfected[0])\r\n",
    "        dirs=[-1,0,1,0,-1]\r\n",
    "\r\n",
    "       \r\n",
    "\r\n",
    "        ret=0\r\n",
    "        while True:\r\n",
    "            neibours=[]\r\n",
    "            firewalls=[]\r\n",
    "            # idx=-1\r\n",
    "            for x in range(R):\r\n",
    "                for y in range(C):\r\n",
    "                    if isInfected[x][y]==1:\r\n",
    "                        idx=len(neibours)+1\r\n",
    "                        queue=[[x,y]]\r\n",
    "                        idx=-idx\r\n",
    "                        isInfected[x][y]=idx\r\n",
    "                        firewall=0\r\n",
    "                        neighbour=set()\r\n",
    "                        while queue:\r\n",
    "                            r,c=queue.pop()\r\n",
    "                            for i in range(4):\r\n",
    "                                nr,nc=r+dirs[i],c+dirs[i+1]\r\n",
    "                                if nr<0 or nr==R or nc<0 or nc==C:\r\n",
    "                                    continue\r\n",
    "                                if isInfected[nr][nc]==1:\r\n",
    "                                    queue.append([nr,nc])\r\n",
    "                                    isInfected[nr][nc]=idx\r\n",
    "                                elif isInfected[nr][nc]==0:\r\n",
    "                                    firewall+=1\r\n",
    "                                    neighbour.add((nr,nc))\r\n",
    "                        neibours.append(neighbour)\r\n",
    "                        firewalls.append(firewall)\r\n",
    "                    \r\n",
    "            if len(neibours)==0:\r\n",
    "                break\r\n",
    "            if len(neibours)==1:\r\n",
    "                ret+=firewalls[0]\r\n",
    "                break\r\n",
    "            idx=0\r\n",
    "            Max=len(neibours[0])\r\n",
    "            for nei in range(1,len(neibours)):\r\n",
    "                if (n:=len(neibours[nei]))>Max:\r\n",
    "                    idx=nei\r\n",
    "                    Max=n\r\n",
    "            ret+=firewalls[idx]\r\n",
    "            tid=-idx-1\r\n",
    "            for r in range(R):\r\n",
    "                for c in range(C):\r\n",
    "                    if isInfected[r][c]<0:\r\n",
    "                        if isInfected[r][c]==tid:\r\n",
    "                            isInfected[r][c]=2\r\n",
    "                        else:\r\n",
    "                            isInfected[r][c]=1\r\n",
    "            \r\n",
    "            for ii,nei in enumerate(neibours):\r\n",
    "                if ii==idx:\r\n",
    "                    continue\r\n",
    "                for r,c in nei:\r\n",
    "                    isInfected[r][c]=1\r\n",
    "    \r\n",
    "\r\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containVirus(self, isInfected: List[List[int]]) -> int:\n",
    "\n",
    "        pos=[(0,1),(0,-1),(1,0),(-1,0)]\n",
    "        m,n=len(isInfected),len(isInfected[0])\n",
    "        res=0\n",
    "\n",
    "        while True:\n",
    "            firewall=[]\n",
    "            neighbors=[]\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if isInfected[i][j]==1:\n",
    "                        # bfs\n",
    "                        q=deque([(i,j)])\n",
    "                        idx=len(neighbors)+1\n",
    "                        neighbor=set()\n",
    "                        cnt=0\n",
    "                        while q:\n",
    "                            # 这里千万不能写i和j变量，不然会影响上面变量，找半天发现不了错在哪\n",
    "                            x,y=q.popleft()\n",
    "                            isInfected[x][y]=-idx                         \n",
    "                            for dx,dy in pos:\n",
    "                                xx,yy=x+dx,y+dy\n",
    "                                if 0<=xx<m and 0<=yy<n:\n",
    "                                    if isInfected[xx][yy]==1:\n",
    "                                        q.append((xx,yy))\n",
    "                                        isInfected[xx][yy]=-idx\n",
    "                                    elif isInfected[xx][yy]==0:\n",
    "                                        neighbor.add((xx,yy))\n",
    "                                        cnt+=1\n",
    "\n",
    "                        # 分别记录每个连通块的大小和所需栅栏\n",
    "                        firewall.append(cnt)\n",
    "                        neighbors.append(neighbor)\n",
    "            # 如果没有可扩展的区域，则退出\n",
    "            if not neighbors:break\n",
    "            print(neighbors)\n",
    "            idx=0\n",
    "            # 首先找向外扩散最大的区域\n",
    "            for i in range(1,len(neighbors)):\n",
    "                if len(neighbors[i])>len(neighbors[idx]):\n",
    "                    idx=i\n",
    "            \n",
    "            # print(idx,spread[idx])\n",
    "            res+=firewall[idx]\n",
    "\n",
    "            # 将最大扩散区域赋值\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if isInfected[i][j]<0:\n",
    "                        if isInfected[i][j]==-(idx+1):\n",
    "                            isInfected[i][j]=inf\n",
    "                        else:\n",
    "                            isInfected[i][j]=1\n",
    "            \n",
    "            # 扩散区域\n",
    "            for i,neighbor in enumerate(neighbors):\n",
    "                if i==idx:continue\n",
    "                for x,y in neighbor:\n",
    "                    isInfected[x][y]=1\n",
    "\n",
    "            # if len(neighbors)==1:break  \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containVirus(self, isInfected: List[List[int]]) -> int:\n",
    "        dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]\n",
    "        \n",
    "        m, n = len(isInfected), len(isInfected[0])\n",
    "        ans = 0\n",
    "\n",
    "        while True:\n",
    "            neighbors, firewalls = list(), list()\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if isInfected[i][j] == 1:\n",
    "                        q = deque([(i, j)])\n",
    "                        neighbor = set()\n",
    "                        firewall, idx = 0, len(neighbors) + 1\n",
    "                        isInfected[i][j] = -idx\n",
    "\n",
    "                        while q:\n",
    "                            x, y = q.popleft()\n",
    "                            for d in range(4):\n",
    "                                nx, ny = x + dirs[d][0], y + dirs[d][1]\n",
    "                                if 0 <= nx < m and 0 <= ny < n:\n",
    "                                    if isInfected[nx][ny] == 1:\n",
    "                                        q.append((nx, ny))\n",
    "                                        isInfected[nx][ny] = -idx\n",
    "                                    elif isInfected[nx][ny] == 0:\n",
    "                                        firewall += 1\n",
    "                                        neighbor.add((nx, ny))\n",
    "                        \n",
    "                        neighbors.append(neighbor)\n",
    "                        firewalls.append(firewall)\n",
    "            \n",
    "            if not neighbors:\n",
    "                break\n",
    "\n",
    "            idx = 0\n",
    "            for i in range(1, len(neighbors)):\n",
    "                if len(neighbors[i]) > len(neighbors[idx]):\n",
    "                    idx = i\n",
    "                \n",
    "            ans += firewalls[idx]\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if isInfected[i][j] < 0:\n",
    "                        if isInfected[i][j] != -idx - 1:\n",
    "                            isInfected[i][j] = 1\n",
    "                        else:\n",
    "                            isInfected[i][j] = 2\n",
    "            \n",
    "            for i, neighbor in enumerate(neighbors):\n",
    "                if i != idx:\n",
    "                    for x, y in neighbor:\n",
    "                        isInfected[x][y] = 1\n",
    "            \n",
    "            if len(neighbors) == 1:\n",
    "                break\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containVirus(self, isInfected: List[List[int]]) -> int:\n",
    "        m, n = len(isInfected), len(isInfected[0]) \n",
    "        ans = 0 \n",
    "        dx = [1, -1, 0, 0]\n",
    "        dy = [0, 0, 1, -1]\n",
    "        \n",
    "        while True:\n",
    "            neis, walls = list(), list() \n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if isInfected[i][j] == 1:\n",
    "                        Q = deque([(i,j)])\n",
    "                        wall, idx = 0, len(neis) + 1\n",
    "                        nei = set() \n",
    "                        isInfected[i][j] = -idx \n",
    "                        while Q:\n",
    "                            x, y = Q.popleft()\n",
    "                            \n",
    "                            for d in range(4):\n",
    "                                nx,ny = x+dx[d], y+dy[d]\n",
    "                                if 0<=nx<m and 0<=ny<n:\n",
    "                                    if isInfected[nx][ny] == 1:\n",
    "                                        Q.append((nx,ny))\n",
    "                                        isInfected[nx][ny] = -idx\n",
    "                                    elif isInfected[nx][ny] == 0:\n",
    "                                        nei.add((nx,ny))\n",
    "                                        wall += 1 \n",
    "                        neis.append(nei)\n",
    "                        walls.append(wall) \n",
    "            if not neis:\n",
    "                break \n",
    "            \n",
    "            idx = 0 \n",
    "            for i in range(1, len(neis)):\n",
    "                if len(neis[i]) > len(neis[idx]):\n",
    "                    idx = i \n",
    "            #print(neis, walls)\n",
    "            #print(idx) \n",
    "            ans += walls[idx]\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if isInfected[i][j] < 0:\n",
    "                        if isInfected[i][j] != -idx-1:\n",
    "                            isInfected[i][j] = 1 \n",
    "                        else:\n",
    "                            isInfected[i][j] = 2 \n",
    "            for i, nei in enumerate(neis):\n",
    "                if i != idx:\n",
    "                    for x, y in nei:\n",
    "                        isInfected[x][y] = 1 \n",
    "            if len(neis) == 1:\n",
    "                break \n",
    "        return ans \n",
    "             \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containVirus(self, isInfected: List[List[int]]) -> int:\n",
    "        dirs=[(-1,0),(1,0),(0,-1),(0,1)]\n",
    "        def scan():\n",
    "            ans=0\n",
    "            m,n=len(isInfected),len(isInfected[0])\n",
    "            neighbors,firewalls=list(),list()\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if isInfected[i][j]==1:\n",
    "                        # 开始bfs\n",
    "                        q=deque([(i,j)])\n",
    "                        neighbor=set()\n",
    "                        firewall=0\n",
    "                        # 这片区域的idx\n",
    "                        idx=len(neighbors)+1\n",
    "                        isInfected[i][j]=-idx\n",
    "                        while q:\n",
    "                            x,y=q.popleft()\n",
    "                            for d in range(4):\n",
    "                                xx=x+dirs[d][0]\n",
    "                                yy=y+dirs[d][1]\n",
    "                                if 0<=xx<m and 0<=yy<n:\n",
    "                                    # 周围的病毒\n",
    "                                    if isInfected[xx][yy]==1:\n",
    "                                        q.append((xx,yy))\n",
    "                                        # 标记为已经访问过\n",
    "                                        isInfected[xx][yy]=-idx\n",
    "                                    elif isInfected[xx][yy]==0:\n",
    "                                        # 可扩散区域\n",
    "                                        neighbor.add((xx,yy))\n",
    "                                        firewall+=1\n",
    "                        # bfs结束，记录此片区域结果\n",
    "                        neighbors.append(neighbor)\n",
    "                        firewalls.append(firewall)\n",
    "            # 不可能扩散了\n",
    "            if not neighbors:\n",
    "                return 0\n",
    "            # 查找当前扩散最严重的区域\n",
    "            idx=0\n",
    "            for i in range(1,len(neighbors)):\n",
    "                if len(neighbors[i])>len(neighbors[idx]):\n",
    "                    idx=i\n",
    "            # 给他装上墙\n",
    "            ans+=firewalls[idx]\n",
    "\n",
    "            # 把不是最危险的区域复原\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    # 存在病毒的区域,所有的点被标记为\n",
    "                    if isInfected[i][j]<0:\n",
    "                        # 不是最危险的区域\n",
    "                        if isInfected[i][j]!=-idx-1:\n",
    "                            isInfected[i][j]=1\n",
    "                        # 是最危险的区域\n",
    "                        else:\n",
    "                            isInfected[i][j]=2\n",
    "            # 让最危险的区域扩散\n",
    "            for i in range(len(neighbors)):\n",
    "                if i!=idx:\n",
    "                    for x,y in neighbors[i]:\n",
    "                        isInfected[x][y]=1\n",
    "            return ans\n",
    "        ret=0\n",
    "        while 1:\n",
    "            need=scan()\n",
    "            if need==0:\n",
    "                break\n",
    "            ret+=need\n",
    "        return ret\n",
    "\n",
    "\n",
    "\n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containVirus(self, isInfected: List[List[int]]) -> int:\n",
    "        m=len(isInfected)\n",
    "        n=len(isInfected[0])\n",
    "        ans=0\n",
    "        while True:\n",
    "            ind=1\n",
    "            neighbor=[]\n",
    "            firwall=[]\n",
    "            for i in range(m): \n",
    "                for j in range(n):\n",
    "                    if isInfected[i][j]==1:\n",
    "                        isInfected[i][j]=-ind\n",
    "                        stack=collections.deque()\n",
    "                        stack.append([i,j])\n",
    "                        tmp=set()\n",
    "                        fw=0\n",
    "                        while stack:\n",
    "                            x,y=stack.popleft()\n",
    "                            for x1,y1 in [[x+1,y],[x-1,y],[x,y+1],[x,y-1]]:\n",
    "                                if 0<=x1<m and 0<=y1<n: \n",
    "                                    if isInfected[x1][y1]==1:\n",
    "                                        isInfected[x1][y1]=-ind\n",
    "                                        stack.append([x1,y1])\n",
    "                                    elif isInfected[x1][y1]==0:\n",
    "                                        tmp.add((x1,y1))\n",
    "                                        fw+=1\n",
    "                        neighbor.append(tmp)\n",
    "                        firwall.append(fw)\n",
    "                        ind+=1\n",
    "           # print(neighbor)\n",
    "            if len(neighbor)==0:\n",
    "                break\n",
    "            mx=firwall[0]\n",
    "            t=0\n",
    "            for i,v in enumerate(neighbor):\n",
    "                if len(v)>mx:\n",
    "                    mx=len(v)\n",
    "                    t=i\n",
    "            ans+=firwall[t] \n",
    "            t=t+1\n",
    "            \n",
    "            for i in range(m): \n",
    "                for j in range(n):\n",
    "                    if isInfected[i][j]==-t:\n",
    "                        isInfected[i][j]=2\n",
    "                    elif isInfected[i][j]<0:\n",
    "                        isInfected[i][j]=1\n",
    "            for i,v in enumerate(neighbor):\n",
    "                if i==(t-1):\n",
    "                    continue\n",
    "                else:\n",
    "                    for x,y in v:\n",
    "                        isInfected[x][y]=1\n",
    "\n",
    "            #if len(neighbor)==1:\n",
    "             #   break\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containVirus(self, isInfected: List[List[int]]) -> int:\n",
    "\n",
    "        pos=[(0,1),(0,-1),(1,0),(-1,0)]\n",
    "        m,n=len(isInfected),len(isInfected[0])\n",
    "        res=0\n",
    "\n",
    "        while True:\n",
    "            firewall=[]\n",
    "            neighbors=[]\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if isInfected[i][j]==1:\n",
    "                        # bfs\n",
    "                        q=deque([(i,j)])\n",
    "                        idx=len(neighbors)+1\n",
    "                        neighbor=set()\n",
    "                        cnt=0\n",
    "                        while q:\n",
    "                            # 这里千万不能写i和j变量，不然会影响上面变量，找半天发现不了错在哪\n",
    "                            x,y=q.popleft()\n",
    "                            isInfected[x][y]=-idx                         \n",
    "                            for dx,dy in pos:\n",
    "                                xx,yy=x+dx,y+dy\n",
    "                                if 0<=xx<m and 0<=yy<n:\n",
    "                                    if isInfected[xx][yy]==1:\n",
    "                                        q.append((xx,yy))\n",
    "                                        isInfected[xx][yy]=-idx\n",
    "                                    elif isInfected[xx][yy]==0:\n",
    "                                        neighbor.add((xx,yy))\n",
    "                                        cnt+=1\n",
    "\n",
    "                        # 分别记录每个连通块的大小和所需栅栏\n",
    "                        firewall.append(cnt)\n",
    "                        neighbors.append(neighbor)\n",
    "            # 如果没有可扩展的区域，则退出\n",
    "            if not neighbors:break\n",
    "            print(neighbors)\n",
    "            idx=0\n",
    "            # 首先找向外扩散最大的区域\n",
    "            for i in range(1,len(neighbors)):\n",
    "                if len(neighbors[i])>len(neighbors[idx]):\n",
    "                    idx=i\n",
    "            \n",
    "            # print(idx,spread[idx])\n",
    "            res+=firewall[idx]\n",
    "\n",
    "            # 将最大扩散区域赋值\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if isInfected[i][j]<0:\n",
    "                        if isInfected[i][j]==-(idx+1):\n",
    "                            isInfected[i][j]=inf\n",
    "                        else:\n",
    "                            isInfected[i][j]=1\n",
    "            \n",
    "            # 扩散区域\n",
    "            for i,neighbor in enumerate(neighbors):\n",
    "                if i==idx:continue\n",
    "                for x,y in neighbor:\n",
    "                    isInfected[x][y]=1\n",
    "            # 如果只剩一个区域，已经安装栅栏，退出\n",
    "            if len(neighbors)==1:break  \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import deque\n",
    "\n",
    "mod = 10 ** 9 + 7\n",
    "\n",
    "dxy = ((-1, 0), (0, 1), (1, 0), (0, -1))\n",
    "\n",
    "class Solution:\n",
    "  def containVirus(self, isInfected: List[List[int]]) -> int:\n",
    "    m, n = len(isInfected), len(isInfected[0])\n",
    "    vis = set()\n",
    "\n",
    "    def cage(x, y):\n",
    "      ans = 0\n",
    "      q = deque()\n",
    "      q.append((x, y))\n",
    "      isInfected[x][y] = 2\n",
    "      while q:\n",
    "        x, y = q.pop()\n",
    "        for dx, dy in dxy:\n",
    "          nx, ny = x + dx, y + dy\n",
    "          if not (0 <= nx < m and 0 <= ny < n): continue\n",
    "          if isInfected[nx][ny] == 1:\n",
    "            q.append((nx, ny))\n",
    "            isInfected[nx][ny] = 2\n",
    "          elif isInfected[nx][ny] == 0:\n",
    "            ans += 1\n",
    "      return ans\n",
    "\n",
    "    def find_range(x, y):\n",
    "      ans_set = set()\n",
    "      q = deque()\n",
    "      q.append((x, y))\n",
    "      vis.add((x, y))\n",
    "      while q:\n",
    "        x, y = q.pop()\n",
    "        for dx, dy in dxy:\n",
    "          nx, ny = x + dx, y + dy\n",
    "          if not (0 <= nx < m and 0 <= ny < n): continue\n",
    "          if (nx, ny) in vis: continue\n",
    "          if isInfected[nx][ny] == 0:\n",
    "            ans_set.add((nx, ny))\n",
    "          elif isInfected[nx][ny] == 1:\n",
    "            q.append((nx, ny))\n",
    "            vis.add((nx, ny))\n",
    "      return len(ans_set)\n",
    "    \n",
    "    def spread(x, y):\n",
    "      q = deque()\n",
    "      q.append((x, y))\n",
    "      vis.add((x, y))\n",
    "      while q:\n",
    "        x, y = q.pop()\n",
    "        for dx, dy in dxy:\n",
    "          nx, ny = x + dx, y + dy\n",
    "          if not (0 <= nx < m and 0 <= ny < n): continue\n",
    "          if (nx, ny) in vis: continue\n",
    "          if isInfected[nx][ny] == 0:\n",
    "            isInfected[nx][ny] = 1\n",
    "            vis.add((nx, ny))\n",
    "          elif isInfected[nx][ny] == 1:\n",
    "            q.append((nx, ny))\n",
    "            vis.add((nx, ny))\n",
    "    \n",
    "    def find_max():\n",
    "      vis.clear()\n",
    "      cur = (-1, -1)\n",
    "      mx = 0\n",
    "      for i in range(m): \n",
    "        for j in range(n):\n",
    "          if isInfected[i][j] != 1 or (i, j) in vis: continue\n",
    "          count = find_range(i, j)\n",
    "          if count > mx:\n",
    "            cur = (i, j)\n",
    "            mx = count\n",
    "      return cur\n",
    "    \n",
    "    def spreads():\n",
    "      vis.clear()\n",
    "      for i in range(m): \n",
    "        for j in range(n):\n",
    "          if isInfected[i][j] != 1 or (i, j) in vis: continue\n",
    "          spread(i, j)\n",
    "    \n",
    "    ans = 0\n",
    "    while True:\n",
    "      x, y = find_max()\n",
    "      if (x, y) == (-1, -1): break\n",
    "      ans += cage(x, y)\n",
    "      spreads()\n",
    "    return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containVirus(self, isInfected: List[List[int]]) -> int:\n",
    "\n",
    "        pos=[(0,1),(0,-1),(1,0),(-1,0)]\n",
    "        m,n=len(isInfected),len(isInfected[0])\n",
    "        res=0\n",
    "\n",
    "        while True:\n",
    "            firewall=[]\n",
    "            neighbors=[]\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if isInfected[i][j]==1:\n",
    "                        # bfs\n",
    "                        q=deque([(i,j)])\n",
    "                        idx=len(neighbors)+1\n",
    "                        neighbor=set()\n",
    "                        cnt=0\n",
    "                        while q:\n",
    "                            i1,j1=q.popleft()\n",
    "                            # if isInfected[i][j]<0:continue   \n",
    "                            isInfected[i1][j1]=-idx                         \n",
    "                            for dx,dy in pos:\n",
    "                                xx,yy=i1+dx,j1+dy\n",
    "                                if 0<=xx<m and 0<=yy<n:\n",
    "                                    if isInfected[xx][yy]==1:\n",
    "                                        q.append((xx,yy))\n",
    "                                        isInfected[xx][yy]=-idx\n",
    "                                    elif isInfected[xx][yy]==0:\n",
    "                                        neighbor.add((xx,yy))\n",
    "                                        cnt+=1\n",
    "\n",
    "                        # 分别记录每个连通块的大小和所需栅栏\n",
    "                        firewall.append(cnt)\n",
    "                        neighbors.append(neighbor)\n",
    "            # 如果没有可扩展的区域，则退出\n",
    "            if not neighbors:break\n",
    "            print(neighbors)\n",
    "            idx=0\n",
    "            # 首先找向外扩散最大的区域\n",
    "            for i in range(1,len(neighbors)):\n",
    "                if len(neighbors[i])>len(neighbors[idx]):\n",
    "                    idx=i\n",
    "            \n",
    "            # print(idx,spread[idx])\n",
    "            res+=firewall[idx]\n",
    "\n",
    "            # 将最大扩散区域赋值\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if isInfected[i][j]<0:\n",
    "                        if isInfected[i][j]==-(idx+1):\n",
    "                            isInfected[i][j]=inf\n",
    "                        else:\n",
    "                            isInfected[i][j]=1\n",
    "            \n",
    "            # 扩散区域\n",
    "            for i,neighbor in enumerate(neighbors):\n",
    "                if i!=idx:\n",
    "                    for x,y in neighbor:\n",
    "                        isInfected[x][y]=1\n",
    "\n",
    "            if len(neighbors)==1:break  \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containVirus(self, isInfected: List[List[int]]) -> int:\n",
    "        m, n = len(isInfected), len(isInfected[0])\n",
    "        directions = [(0,1),(0,-1),(1,0),(-1,0)]\n",
    "        fa = list(range(m*n))\n",
    "        def find(x):\n",
    "            if fa[x] != x:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "\n",
    "        def oneNight():\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if isInfected[i][j] == 1:\n",
    "                        for di,dj in directions:\n",
    "                            a, b = i+di, j+dj\n",
    "                            if 0 <= a < m and 0 <= b < n and isInfected[a][b] == 1:\n",
    "                                fa[find(i*n+j)] = find(a*n+b)\n",
    "            \n",
    "            d = defaultdict(list)\n",
    "            c = Counter()\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    p = find(i*n+j)\n",
    "                    if isInfected[i][j] == 1:\n",
    "                        d[p].append((i,j))\n",
    "\n",
    "            neighbor = defaultdict(set)\n",
    "            for p in d:\n",
    "                neighbor[p], c[p] = canInfect(d[p])\n",
    "            if not c:\n",
    "                return 0\n",
    "            mx = max(len(s) for s in neighbor.values())\n",
    "            for p in d:\n",
    "                if len(neighbor[p]) == mx:\n",
    "                    ans = c[p]\n",
    "                    for i,j in d[p]:\n",
    "                        isInfected[i][j] = -1\n",
    "                else:\n",
    "                    for i,j in neighbor[p]:\n",
    "                        isInfected[i][j] = 1\n",
    "            return ans\n",
    "\n",
    "        def canInfect(q):\n",
    "            s, wall = set(), 0\n",
    "            for i,j in q:\n",
    "                for di,dj in directions:\n",
    "                    a, b = i+di, j+dj\n",
    "                    if 0 <= a < m and 0 <= b < n and isInfected[a][b] == 0:\n",
    "                            s.add((a,b))\n",
    "                            wall += 1\n",
    "            return s, wall\n",
    "\n",
    "        ans = 0\n",
    "        while (x := oneNight()) > 0:\n",
    "            ans += x\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import deque\n",
    "\n",
    "dxy = ((-1, 0), (0, 1), (1, 0), (0, -1))\n",
    "\n",
    "class Solution:\n",
    "  def containVirus(self, isInfected: List[List[int]]) -> int:\n",
    "    m, n = len(isInfected), len(isInfected[0])\n",
    "    vis = set()\n",
    "\n",
    "    def cage(x, y):\n",
    "      ans = 0\n",
    "      q = deque()\n",
    "      q.append((x, y))\n",
    "      isInfected[x][y] = 2\n",
    "      while q:\n",
    "        x, y = q.pop()\n",
    "        for dx, dy in dxy:\n",
    "          nx, ny = x + dx, y + dy\n",
    "          if not (0 <= nx < m and 0 <= ny < n): continue\n",
    "          if isInfected[nx][ny] == 1:\n",
    "            q.append((nx, ny))\n",
    "            isInfected[nx][ny] = 2\n",
    "          elif isInfected[nx][ny] == 0:\n",
    "            ans += 1\n",
    "      return ans\n",
    "\n",
    "    def find_range(x, y):\n",
    "      ans_set = set()\n",
    "      q = deque()\n",
    "      q.append((x, y))\n",
    "      vis.add((x, y))\n",
    "      while q:\n",
    "        x, y = q.pop()\n",
    "        for dx, dy in dxy:\n",
    "          nx, ny = x + dx, y + dy\n",
    "          if not (0 <= nx < m and 0 <= ny < n): continue\n",
    "          if (nx, ny) in vis: continue\n",
    "          if isInfected[nx][ny] == 0:\n",
    "            ans_set.add((nx, ny))\n",
    "          elif isInfected[nx][ny] == 1:\n",
    "            q.append((nx, ny))\n",
    "            vis.add((nx, ny))\n",
    "      return len(ans_set)\n",
    "    \n",
    "    def spread(x, y):\n",
    "      q = deque()\n",
    "      q.append((x, y))\n",
    "      vis.add((x, y))\n",
    "      while q:\n",
    "        x, y = q.pop()\n",
    "        for dx, dy in dxy:\n",
    "          nx, ny = x + dx, y + dy\n",
    "          if not (0 <= nx < m and 0 <= ny < n): continue\n",
    "          if (nx, ny) in vis: continue\n",
    "          if isInfected[nx][ny] == 0:\n",
    "            isInfected[nx][ny] = 1\n",
    "            vis.add((nx, ny))\n",
    "          elif isInfected[nx][ny] == 1:\n",
    "            q.append((nx, ny))\n",
    "            vis.add((nx, ny))\n",
    "    \n",
    "    def find_max():\n",
    "      vis.clear()\n",
    "      cur = (-1, -1)\n",
    "      mx = 0\n",
    "      for i in range(m): \n",
    "        for j in range(n):\n",
    "          if isInfected[i][j] != 1 or (i, j) in vis: continue\n",
    "          count = find_range(i, j)\n",
    "          if count > mx:\n",
    "            cur = (i, j)\n",
    "            mx = count\n",
    "      return cur\n",
    "    \n",
    "    def spreads():\n",
    "      vis.clear()\n",
    "      for i in range(m): \n",
    "        for j in range(n):\n",
    "          if isInfected[i][j] != 1 or (i, j) in vis: continue\n",
    "          spread(i, j)\n",
    "    \n",
    "    ans = 0\n",
    "    while True:\n",
    "      x, y = find_max()\n",
    "      if (x, y) == (-1, -1): break\n",
    "      ans += cage(x, y)\n",
    "      spreads()\n",
    "    return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containVirus(self, isInfected: List[List[int]]) -> int:\n",
    "        '''\n",
    "        Change list to set\n",
    "        '''\n",
    "        m, n = len(isInfected), len(isInfected[0])\n",
    "\n",
    "        # The _areaAdt is key/value dict\n",
    "        # The key is root of adt, \n",
    "        # The value is the list which contains the continuous blocks of virus belong to root\n",
    "        # The elements of value of list, is the position which has virus\n",
    "        # position = x * n + y, \n",
    "        #   x, y is the index of isInfected\n",
    "        #   n is the columns of isInfected\n",
    "        _areaAdt = {}\n",
    "        adt = [-1] * (m*n)\n",
    "\n",
    "        # The element of wall is tuple(cell1, cell2)\n",
    "        #   cell1 < cell2\n",
    "        #   cell = x * m + y, \n",
    "        walls = set()\n",
    "        \n",
    "        def find(x:int) -> int:\n",
    "            if adt[x] < 0:\n",
    "                return x\n",
    "            else:\n",
    "                adt[x] = find(adt[x])\n",
    "                return adt[x]\n",
    "\n",
    "        def union(x:int, y:int):\n",
    "            '''\n",
    "            union the adt and return the position\n",
    "            '''\n",
    "            root1, root2 = find(x), find(y)\n",
    "            if root1 == root2: return\n",
    "\n",
    "            root, child = 0, 0\n",
    "            if adt[root2] < adt[root1]:\n",
    "                # root 2 is deeper\n",
    "                adt[root1] = root2\n",
    "                root, child = root2, root1\n",
    "            else:\n",
    "                if adt[root2] == adt[root1]:\n",
    "                    adt[root1] -= 1\n",
    "                adt[root2] = root1\n",
    "                root, child = root1, root2\n",
    "            \n",
    "            if root not in _areaAdt.keys():\n",
    "                _areaAdt[root] = [x if root == root1 else y]\n",
    "\n",
    "            if child not in _areaAdt.keys():\n",
    "                _areaAdt[root].append(y if root == root1 else x)\n",
    "            else:\n",
    "                _areaAdt[root].extend(_areaAdt[child])\n",
    "                del _areaAdt[child]\n",
    "\n",
    "        # Initial the areas\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if j+1 < n and isInfected[i][j] == isInfected[i][j+1] == 1:\n",
    "                    union(i*n+j, i*n+j+1)\n",
    "                if i+1 < m and isInfected[i][j] == isInfected[i+1][j] == 1:\n",
    "                    union(i*n+j, (i+1)*n+j)\n",
    "                if isInfected[i][j] == 1 and find(i*n+j) not in _areaAdt.keys():\n",
    "                    _areaAdt[find(i*n+j)] = [i*n+j]\n",
    "        \n",
    "        def isWall(x, y, _x, _y):\n",
    "            pos1 = x * n + y\n",
    "            pos2 = (x+_x) * m + y+_y\n",
    "            if (min(pos1, pos2), max(pos1, pos2)) in walls:\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "\n",
    "        def nextAreas():\n",
    "            roots, cntL, cntPosL = [], [], []\n",
    "\n",
    "            for key in _areaAdt.keys():\n",
    "                cl = set()\n",
    "                \n",
    "                for pos in _areaAdt[key]:\n",
    "                    x, y = pos // n, pos % n\n",
    "                    for _x, _y in [(0,1),(0,-1),(-1,0),(1,0)]:\n",
    "                        if 0<=x+_x<m and 0<=y+_y<n and isInfected[x+_x][y+_y]==0 and not isWall(x,y,_x,_y) and (x+_x)*n+y+_y not in cl:\n",
    "                            cl.add((x+_x)*n+y+_y)\n",
    "                \n",
    "                roots.append(key)\n",
    "                cntL.append(len(cl))\n",
    "                cntPosL.append(list(cl))\n",
    "\n",
    "            return roots, cntL, cntPosL\n",
    "        \n",
    "        roots, cnt, posL = nextAreas()\n",
    "        while cnt and max(cnt) > 0:\n",
    "            inx = cnt.index(max(cnt))\n",
    "            # install wall\n",
    "            for pos in posL[inx]:\n",
    "                x, y = pos // n, pos % n\n",
    "                for _x, _y in [(0,1),(0,-1),(-1,0),(1,0)]:\n",
    "                    if 0<=x+_x<m and 0<=y+_y<n and (x+_x)*n+y+_y in _areaAdt[roots[inx]]:\n",
    "                        if (min(pos, (x+_x)*n+y+_y),max(pos, (x+_x)*n+y+_y)) not in walls:\n",
    "                            walls.add((min(pos, (x+_x)*n+y+_y),max(pos, (x+_x)*n+y+_y)))\n",
    "            \n",
    "            # clear the area of install wall\n",
    "            del _areaAdt[roots[inx]]\n",
    "            \n",
    "            # infect\n",
    "            for i in range(len(posL)):\n",
    "                if i == inx: continue\n",
    "                for pos in posL[i]:\n",
    "                    x, y = pos // n, pos % n\n",
    "                    isInfected[x][y] = 1\n",
    "                    for _x, _y in [(0,1),(0,-1),(-1,0),(1,0)]:\n",
    "                        if 0<=x+_x<m and 0<=y+_y<n and isInfected[x+_x][y+_y] == 1 and not isWall(x,y,_x,_y):\n",
    "                            union(pos, (x+_x)*n+y+_y)\n",
    "\n",
    "            roots, cnt, posL = nextAreas()\n",
    "\n",
    "        return len(walls)        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containVirus(self, isInfected: List[List[int]]) -> int:\n",
    "        m, n = len(isInfected), len(isInfected[0])\n",
    "\n",
    "        # The _areaAdt is key/value dict\n",
    "        # The key is root of adt, \n",
    "        # The value is the list which contains the continuous blocks of virus belong to root\n",
    "        # The elements of value of list, is the position which has virus\n",
    "        # position = x * n + y, \n",
    "        #   x, y is the index of isInfected\n",
    "        #   n is the columns of isInfected\n",
    "        _areaAdt = {}\n",
    "        adt = [-1] * (m*n)\n",
    "\n",
    "        # The element of wall is tuple(cell1, cell2)\n",
    "        #   cell1 < cell2\n",
    "        #   cell = x * m + y, \n",
    "        walls = []\n",
    "        \n",
    "        def find(x:int) -> int:\n",
    "            if adt[x] < 0:\n",
    "                return x\n",
    "            else:\n",
    "                adt[x] = find(adt[x])\n",
    "                return adt[x]\n",
    "\n",
    "        def union(x:int, y:int):\n",
    "            '''\n",
    "            union the adt and return the position\n",
    "            '''\n",
    "            root1, root2 = find(x), find(y)\n",
    "            if root1 == root2: return\n",
    "\n",
    "            root, child = 0, 0\n",
    "            if adt[root2] < adt[root1]:\n",
    "                # root 2 is deeper\n",
    "                adt[root1] = root2\n",
    "                root, child = root2, root1\n",
    "            else:\n",
    "                if adt[root2] == adt[root1]:\n",
    "                    adt[root1] -= 1\n",
    "                adt[root2] = root1\n",
    "                root, child = root1, root2\n",
    "            \n",
    "            if root not in _areaAdt.keys():\n",
    "                _areaAdt[root] = [x if root == root1 else y]\n",
    "\n",
    "            if child not in _areaAdt.keys():\n",
    "                _areaAdt[root].append(y if root == root1 else x)\n",
    "            else:\n",
    "                _areaAdt[root].extend(_areaAdt[child])\n",
    "                del _areaAdt[child]\n",
    "\n",
    "        # Initial the areas\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if j+1 < n and isInfected[i][j] == isInfected[i][j+1] == 1:\n",
    "                    union(i*n+j, i*n+j+1)\n",
    "                if i+1 < m and isInfected[i][j] == isInfected[i+1][j] == 1:\n",
    "                    union(i*n+j, (i+1)*n+j)\n",
    "                if isInfected[i][j] == 1 and find(i*n+j) not in _areaAdt.keys():\n",
    "                    _areaAdt[find(i*n+j)] = [i*n+j]\n",
    "        \n",
    "        def isWall(x, y, _x, _y):\n",
    "            pos1 = x * n + y\n",
    "            pos2 = (x+_x) * m + y+_y\n",
    "            if (min(pos1, pos2), max(pos1, pos2)) in walls:\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "\n",
    "        def nextAreas():\n",
    "            roots, cntL, cntPosL = [], [], []\n",
    "\n",
    "            for key in _areaAdt.keys():\n",
    "                cl =[]\n",
    "                \n",
    "                for pos in _areaAdt[key]:\n",
    "                    x, y = pos // n, pos % n\n",
    "                    for _x, _y in [(0,1),(0,-1),(-1,0),(1,0)]:\n",
    "                        if 0<=x+_x<m and 0<=y+_y<n and isInfected[x+_x][y+_y]==0 and not isWall(x,y,_x,_y) and (x+_x)*n+y+_y not in cl:\n",
    "                            cl.append((x+_x)*n+y+_y)\n",
    "                \n",
    "                roots.append(key)\n",
    "                cntL.append(len(cl))\n",
    "                cntPosL.append(cl)\n",
    "\n",
    "            return roots, cntL, cntPosL\n",
    "        \n",
    "        roots, cnt, posL = nextAreas()\n",
    "        while cnt and max(cnt) > 0:\n",
    "            inx = cnt.index(max(cnt))\n",
    "            # install wall\n",
    "            for pos in posL[inx]:\n",
    "                x, y = pos // n, pos % n\n",
    "                for _x, _y in [(0,1),(0,-1),(-1,0),(1,0)]:\n",
    "                    if 0<=x+_x<m and 0<=y+_y<n and (x+_x)*n+y+_y in _areaAdt[roots[inx]]:\n",
    "                        if (min(pos, (x+_x)*n+y+_y),max(pos, (x+_x)*n+y+_y)) not in walls:\n",
    "                            walls.append((min(pos, (x+_x)*n+y+_y),max(pos, (x+_x)*n+y+_y)))\n",
    "            \n",
    "            # clear the area of install wall\n",
    "            del _areaAdt[roots[inx]]\n",
    "            \n",
    "            # infect\n",
    "            for i in range(len(posL)):\n",
    "                if i == inx: continue\n",
    "                for pos in posL[i]:\n",
    "                    x, y = pos // n, pos % n\n",
    "                    isInfected[x][y] = 1\n",
    "                    for _x, _y in [(0,1),(0,-1),(-1,0),(1,0)]:\n",
    "                        if 0<=x+_x<m and 0<=y+_y<n and isInfected[x+_x][y+_y] == 1 and not isWall(x,y,_x,_y):\n",
    "                            union(pos, (x+_x)*n+y+_y)\n",
    "\n",
    "            roots, cnt, posL = nextAreas()\n",
    "\n",
    "        return len(walls)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containVirus(self, isInfected: List[List[int]]) -> int:\n",
    "        m, n = len(isInfected), len(isInfected[0])\n",
    "\n",
    "        # The areas contains the continuous blocks of virus\n",
    "        # The areas_wall contains the continuous blocks of\n",
    "        # virus which have installed the wall\n",
    "        # The elements of areas, areas_wall is the list of\n",
    "        # position which has virus\n",
    "        # position = x * n + y, \n",
    "        #   x, y is the index of isInfected\n",
    "        #   n is the columns of isInfected\n",
    "        _areaInx = {}\n",
    "        _areas, _areas_wall = [], []\n",
    "\n",
    "        # The element of wall is tuple(cell1, cell2)\n",
    "        #   cell1 < cell2\n",
    "        #   cell = x * m + y, \n",
    "        walls = []\n",
    "        \n",
    "        adt = [-1] * (m*n)\n",
    "        \n",
    "        def find(x:int) -> int:\n",
    "            if adt[x] < 0:\n",
    "                return x\n",
    "            else:\n",
    "                adt[x] = find(adt[x])\n",
    "                return adt[x]\n",
    "\n",
    "        def union(x:int, y:int):\n",
    "            '''\n",
    "            union the adt and return the position\n",
    "            '''\n",
    "            root1, root2 = find(x), find(y)\n",
    "            if root1 == root2: return\n",
    "\n",
    "            root, child = 0, 0\n",
    "            if adt[root2] < adt[root1]:\n",
    "                # root 2 is deeper\n",
    "                adt[root1] = root2\n",
    "                root, child = root2, root1\n",
    "            else:\n",
    "                if adt[root2] == adt[root1]:\n",
    "                    adt[root1] -= 1\n",
    "                adt[root2] = root1\n",
    "                root, child = root1, root2\n",
    "            \n",
    "            if root not in _areaInx.keys():\n",
    "                _areas.append([x if root == root1 else y])\n",
    "                _areaInx[root] = len(_areas) - 1\n",
    "\n",
    "            if child not in _areaInx.keys():\n",
    "                _areas[_areaInx[root]].append(y if root == root1 else x)\n",
    "            else:\n",
    "                _areas[_areaInx[root]].extend(_areas[_areaInx[child]])\n",
    "                _areas[_areaInx[child]] = []\n",
    "\n",
    "        # Initial the areas\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if j+1 < n and isInfected[i][j] == isInfected[i][j+1] == 1:\n",
    "                    union(i*n+j, i*n+j+1)\n",
    "                if i+1 < m and isInfected[i][j] == isInfected[i+1][j] == 1:\n",
    "                    union(i*n+j, (i+1)*n+j)\n",
    "                if isInfected[i][j] == 1 and find(i*n+j) not in _areaInx.keys():\n",
    "                    _areas.append([i*n+j])\n",
    "                    _areaInx[find(i*n+j)] = len(_areas) - 1\n",
    "        \n",
    "        def isWall(x, y, _x, _y):\n",
    "            pos1 = x * n + y\n",
    "            pos2 = (x+_x) * m + y+_y\n",
    "            if (min(pos1, pos2), max(pos1, pos2)) in walls:\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "\n",
    "        def nextAreas():\n",
    "            areaL, cntL, cntPosL = [], [], []\n",
    "\n",
    "            for i in range(len(_areas)):\n",
    "                cl =[]\n",
    "                \n",
    "                for pos in _areas[i]:\n",
    "                    x, y = pos // n, pos % n\n",
    "                    for _x, _y in [(0,1),(0,-1),(-1,0),(1,0)]:\n",
    "                        if 0<=x+_x<m and 0<=y+_y<n and isInfected[x+_x][y+_y]==0 and not isWall(x,y,_x,_y) and (x+_x)*n+y+_y not in cl:\n",
    "                            cl.append((x+_x)*n+y+_y)\n",
    "                \n",
    "                areaL.append(i)\n",
    "                cntL.append(len(cl))\n",
    "                cntPosL.append(cl)\n",
    "\n",
    "            return areaL, cntL, cntPosL\n",
    "        \n",
    "        areaI, cnt, posL = nextAreas()\n",
    "        while cnt and max(cnt) > 0:\n",
    "            inx = cnt.index(max(cnt))\n",
    "            # install wall\n",
    "            for pos in posL[inx]:\n",
    "                x, y = pos // n, pos % n\n",
    "                for _x, _y in [(0,1),(0,-1),(-1,0),(1,0)]:\n",
    "                    if 0<=x+_x<m and 0<=y+_y<n and (x+_x)*n+y+_y in _areas[areaI[inx]]:\n",
    "                        if (min(pos, (x+_x)*n+y+_y),max(pos, (x+_x)*n+y+_y)) not in walls:\n",
    "                            walls.append((min(pos, (x+_x)*n+y+_y),max(pos, (x+_x)*n+y+_y)))\n",
    "            \n",
    "            # clear the area of install wall\n",
    "            _areas[areaI[inx]] = []\n",
    "            \n",
    "            # infect\n",
    "            for i in range(len(posL)):\n",
    "                if i == inx: continue\n",
    "                for pos in posL[i]:\n",
    "                    x, y = pos // n, pos % n\n",
    "                    isInfected[x][y] = 1\n",
    "                    for _x, _y in [(0,1),(0,-1),(-1,0),(1,0)]:\n",
    "                        if 0<=x+_x<m and 0<=y+_y<n and isInfected[x+_x][y+_y] == 1 and not isWall(x,y,_x,_y):\n",
    "                            union(pos, (x+_x)*n+y+_y)\n",
    "\n",
    "            areaI, cnt, posL = nextAreas()\n",
    "\n",
    "        return len(walls)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containVirus(self, grid: List[List[int]]) -> int:\n",
    "        m , n = len(grid) , len(grid[0])\n",
    "        deads = [[False for _ in range(n)] for _ in range(m)]\n",
    "        direction = [[0,1],[1,0],[0,-1],[-1,0]]\n",
    "\n",
    "        def bfs(i,j):\n",
    "            # grid[i][j] = 2\n",
    "            # x = set()\n",
    "            # y = set()\n",
    "            # y.add((i,j))\n",
    "            # k = 0\n",
    "            # for di , dj in direction:\n",
    "            #     ni , nj = i + di , j + dj\n",
    "            #     if 0 <= ni < m and 0 <= nj < n and grid[ni][nj] == 1 and not deads[ni][nj]:\n",
    "            #         ans = dfs(ni,nj)\n",
    "            #         x |= ans[1]\n",
    "            #         y |= ans[2]\n",
    "            #         k += ans[0]\n",
    "            #     elif 0 <= ni < m and 0 <= nj < n and grid[ni][nj] == 0:\n",
    "            #         x.add((ni,nj))\n",
    "            #         k += 1\n",
    "            # return (k,x,y)\n",
    "            k , x , y = 0 , set() , set()\n",
    "            queue = deque([(i,j)])\n",
    "            y.add((i,j))\n",
    "            visited.add((i,j))\n",
    "            while queue:\n",
    "                i , j = queue.popleft()\n",
    "                for di , dj in direction:\n",
    "                    ni , nj = i + di , j + dj\n",
    "                    if 0 <= ni < m and 0 <= nj < n:\n",
    "                        if (ni,nj) not in visited and grid[ni][nj] == 1 and not deads[ni][nj]:\n",
    "                            visited.add((ni,nj))\n",
    "                            y.add((ni,nj))\n",
    "                            queue.append((ni,nj))\n",
    "                        if grid[ni][nj] == 0:\n",
    "                            k += 1\n",
    "                            x.add((ni,nj))\n",
    "            return k , x , y\n",
    "        def getWall():\n",
    "            q = []\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if grid[i][j] == 1 and not deads[i][j] and (i,j) not in visited:\n",
    "                        k , x , y = bfs(i,j)\n",
    "                        heapq.heappush(q,(-len(x),k,x,y))\n",
    "            return q\n",
    "\n",
    "        visited = set()\n",
    "        queue = getWall()\n",
    "        \n",
    "        ans = 0\n",
    "        while queue:\n",
    "            visited = set()\n",
    "            _ , k , _ , y = heapq.heappop(queue)\n",
    "            for i , j in y:\n",
    "                deads[i][j] = True\n",
    "            ans += k\n",
    "            for _ , _ , x , y in queue:\n",
    "                for i , j in x:\n",
    "                    grid[i][j] = 1\n",
    "                for i , j in y:\n",
    "                    grid[i][j] = 1\n",
    "            queue = getWall()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containVirus(self, isInfected: List[List[int]]) -> int:\n",
    "        self.w = len(isInfected[0])\n",
    "        self.h = len(isInfected)\n",
    "        self.m = copy.deepcopy(isInfected)\n",
    "        tmp = copy.deepcopy(isInfected)\n",
    "        res = 0\n",
    "        flag0 = 1\n",
    "        sizemax = 1\n",
    "        while flag0 == 1:\n",
    "            sizemax = 0\n",
    "            xmax = 0\n",
    "            ymax = 0\n",
    "            flag0 = 0\n",
    "            for i in range(self.h):\n",
    "                for j in range(self.w):\n",
    "                    self.s = set()\n",
    "                    self.wall = 0\n",
    "                    self.vir = []\n",
    "                    self.al = []\n",
    "                    if self.m[i][j] == 1:\n",
    "                        self.delvirus(i, j)\n",
    "                        #print(self.s)\n",
    "                        if len(self.s) > sizemax:\n",
    "                            sizemax = len(self.s)\n",
    "                            xmax = i\n",
    "                            ymax = j\n",
    "            if sizemax == 0:\n",
    "                break\n",
    "            self.m = copy.deepcopy(tmp)                \n",
    "            print(sizemax, xmax, ymax, self.m[xmax][ymax])\n",
    "            self.wall = 0\n",
    "            self.delvirus(xmax, ymax)\n",
    "            tmp = copy.deepcopy(self.m)\n",
    "            res += self.wall\n",
    "            #print(res)\n",
    "            self.add = []\n",
    "            for i in range(self.h):\n",
    "                for j in range(self.w):\n",
    "                    if self.m[i][j] == 1:\n",
    "                        self.nextday(i, j)\n",
    "                        flag0 = 1\n",
    "            for i in self.add:\n",
    "                self.m[i[0]][i[1]] = 1\n",
    "            #print(self.m)\n",
    "            tmp = copy.deepcopy(self.m)\n",
    "            \n",
    "        return res   \n",
    "\n",
    "    def nextday(self,x,y):\n",
    "        if x > 0 and self.m[x-1][y] == 0:\n",
    "            self.add.append([x-1, y])\n",
    "        if x < self.h-1 and self.m[x+1][y] == 0:\n",
    "            self.add.append([x+1, y])\n",
    "        if y > 0 and self.m[x][y-1] == 0:\n",
    "            self.add.append([x, y-1])\n",
    "        if y < self.w-1 and self.m[x][y+1] == 0:\n",
    "            self.add.append([x, y+1])\n",
    "\n",
    "\n",
    "    def delvirus(self, x ,y):\n",
    "        self.vir.append([x,y])\n",
    "        self.m[x][y] = -1\n",
    "\n",
    "        if x > 0 and [x-1, y] not in self.vir:\n",
    "            if self.m[x-1][y] == 1:\n",
    "                self.delvirus(x-1, y)\n",
    "            elif self.m[x-1][y] == 0:\n",
    "                self.al.append([x-1,y])\n",
    "                self.s.add((x-1, y))\n",
    "                self.wall += 1\n",
    "        if x < self.h-1 and [x+1, y] not in self.vir:\n",
    "            if self.m[x+1][y] == 1 :\n",
    "                self.delvirus(x+1, y)\n",
    "            elif self.m[x+1][y] == 0:\n",
    "                self.al.append([x+1,y])\n",
    "                self.s.add((x+1, y))\n",
    "                self.wall += 1\n",
    "        if y > 0 and [x, y-1] not in self.vir:\n",
    "            if self.m[x][y-1] == 1:\n",
    "                self.delvirus(x, y-1)\n",
    "            elif self.m[x][y-1] == 0:\n",
    "                self.al.append([x,y-1])\n",
    "                self.s.add((x, y-1))\n",
    "                self.wall += 1\n",
    "        if y < self.w-1 and [x, y+1] not in self.vir:\n",
    "            if self.m[x][y+1] == 1:\n",
    "                self.delvirus(x, y+1)\n",
    "            elif self.m[x][y+1] == 0:\n",
    "                self.al.append([x,y-1])\n",
    "                self.s.add((x, y+1))\n",
    "                self.wall += 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containVirus(self, isInfected: List[List[int]]) -> int:\n",
    "        self.m=len(isInfected)\n",
    "        self.n=len(isInfected[0])\n",
    "        self.isInfected=isInfected\n",
    "        ch=True\n",
    "        wall=0\n",
    "        chr0=0\n",
    "        self.visited=[[False for _ in range(self.n) ] for _ in range(self.m)]\n",
    "        while ch:\n",
    "            chr0+=1\n",
    "            for x in self.isInfected:\n",
    "                print(x)\n",
    "            self.visited=[[False for _ in range(self.n) ] for _ in range(self.m)]\n",
    "            tempv=[]\n",
    "            for i in range(self.m):\n",
    "                for j in range(self.n):\n",
    "                    if self.isInfected[i][j]==1 and self.visited[i][j]==False:\n",
    "                        import copy\n",
    "                        v2=copy.deepcopy(self.visited)\n",
    "                        r = self.add3(i, j)\n",
    "                        self.visited=[i for i in v2]\n",
    "                        t = self.sub3(i, j)\n",
    "                        if r==0 or t==0:\n",
    "                            continue\n",
    "                        tempv.append([r,i,j,t])\n",
    "                        \n",
    "            self.visited=[[False for _ in range(self.n) ] for _ in range(self.m)]\n",
    "            print(tempv)\n",
    "            \n",
    "            if tempv==[]:\n",
    "                break\n",
    "            tempv.sort()\n",
    "            print(tempv)\n",
    "            wall+=tempv[-1][3]\n",
    "            \n",
    "            print(wall)\n",
    "            self.addwall(tempv[-1][1],tempv[-1][2])\n",
    "            if len(tempv)==1:\n",
    "                break\n",
    "            for i in range(self.m):\n",
    "                for j in range(self.n):\n",
    "                    if self.isInfected[i][j]==1 and self.visited[i][j]==False:\n",
    "                        self.boost(i,j)\n",
    "            \n",
    "        return wall\n",
    "    \n",
    "    def boost(self,i,j):\n",
    "        self.visited[i][j]=True\n",
    "        if self.border(i-1,j):\n",
    "            if self.isInfected[i-1][j]==1 and self.visited[i-1][j]==False:\n",
    "                self.boost(i-1,j)\n",
    "            if self.isInfected[i-1][j]==0:\n",
    "                self.isInfected[i-1][j]=1\n",
    "                self.visited[i-1][j]=True\n",
    "        if self.border(i+1,j):\n",
    "            if self.isInfected[i+1][j]==1 and self.visited[i+1][j]==False:\n",
    "                self.boost(i+1,j)\n",
    "            if self.isInfected[i+1][j]==0:\n",
    "                self.isInfected[i+1][j]=1\n",
    "                self.visited[i+1][j]=True\n",
    "        if self.border(i,j-1):\n",
    "            if self.isInfected[i][j-1]==1 and self.visited[i][j-1]==False:\n",
    "                self.boost(i,j-1)\n",
    "            if self.isInfected[i][j-1]==0:\n",
    "                self.isInfected[i][j-1]=1\n",
    "                self.visited[i][j-1]=True\n",
    "        if self.border(i,j+1):\n",
    "            if self.isInfected[i][j+1]==1 and self.visited[i][j+1]==False:\n",
    "                self.boost(i,j+1)\n",
    "            if self.isInfected[i][j+1]==0:\n",
    "                self.isInfected[i][j+1]=1\n",
    "                self.visited[i][j+1]=True\n",
    "\n",
    "    def add3(self,i,j):\n",
    "        self.visited[i][j]=True\n",
    "        res=0\n",
    "        if self.border(i-1,j):\n",
    "            if self.isInfected[i-1][j]==1 and self.visited[i-1][j]==False:\n",
    "                res+=self.add3(i-1,j)\n",
    "            if self.isInfected[i-1][j]==0:\n",
    "                self.isInfected[i-1][j]=3\n",
    "                res+=1\n",
    "        if self.border(i+1,j):\n",
    "            if self.isInfected[i+1][j]==1 and self.visited[i+1][j]==False:\n",
    "                res+=self.add3(i+1,j)\n",
    "            if self.isInfected[i+1][j]==0:\n",
    "                self.isInfected[i+1][j]=3\n",
    "                res+=1\n",
    "        if self.border(i,j-1):\n",
    "            if self.isInfected[i][j-1]==1 and self.visited[i][j-1]==False:\n",
    "                res+=self.add3(i,j-1)\n",
    "            if self.isInfected[i][j-1]==0:\n",
    "                self.isInfected[i][j-1]=3\n",
    "                res+=1\n",
    "        if self.border(i,j+1):\n",
    "            if self.isInfected[i][j+1]==1 and self.visited[i][j+1]==False:\n",
    "                res+=self.add3(i,j+1)\n",
    "            if self.isInfected[i][j+1]==0:\n",
    "                self.isInfected[i][j+1]=3\n",
    "                res+=1\n",
    "        #self.visited[i][j]=False\n",
    "        return res\n",
    "\n",
    "    def sub3(self,i,j):\n",
    "        self.visited[i][j]=True\n",
    "        res=0\n",
    "        if self.border(i-1,j):\n",
    "            if self.isInfected[i-1][j]==1 and self.visited[i-1][j]==False:\n",
    "                res+=self.sub3(i-1,j)\n",
    "            if self.isInfected[i-1][j]==3:\n",
    "                self.isInfected[i-1][j]=0\n",
    "            if self.isInfected[i-1][j]==0:\n",
    "                res+=1\n",
    "        if self.border(i+1,j):\n",
    "            if self.isInfected[i+1][j]==1 and self.visited[i+1][j]==False:\n",
    "                res+=self.sub3(i+1,j)\n",
    "            if self.isInfected[i+1][j]==3:\n",
    "                self.isInfected[i+1][j]=0\n",
    "            if self.isInfected[i+1][j]==0:\n",
    "                res+=1\n",
    "        if self.border(i,j-1):\n",
    "            if self.isInfected[i][j-1]==1 and self.visited[i][j-1]==False:\n",
    "                res+=self.sub3(i,j-1)\n",
    "            if self.isInfected[i][j-1]==3:\n",
    "                self.isInfected[i][j-1]=0\n",
    "            if self.isInfected[i][j-1]==0:\n",
    "                res+=1\n",
    "        if self.border(i,j+1):\n",
    "            if self.isInfected[i][j+1]==1 and self.visited[i][j+1]==False:\n",
    "                res+=self.sub3(i,j+1)\n",
    "            if self.isInfected[i][j+1]==3:\n",
    "                self.isInfected[i][j+1]=0\n",
    "            if self.isInfected[i][j+1]==0:\n",
    "                res+=1\n",
    "        return res\n",
    "    \n",
    "    def addwall(self,i,j):\n",
    "        self.visited[i][j]=True\n",
    "        self.isInfected[i][j]=-1\n",
    "        if self.border(i-1,j):\n",
    "            if self.isInfected[i-1][j]==1 and self.visited[i-1][j]==False:\n",
    "                self.addwall(i-1,j)\n",
    "        if self.border(i+1,j):\n",
    "            if self.isInfected[i+1][j]==1 and self.visited[i+1][j]==False:\n",
    "                self.addwall(i+1,j)\n",
    "        if self.border(i,j-1):\n",
    "            if self.isInfected[i][j-1]==1 and self.visited[i][j-1]==False:\n",
    "                self.addwall(i,j-1)\n",
    "        if self.border(i,j+1):\n",
    "            if self.isInfected[i][j+1]==1 and self.visited[i][j+1]==False:\n",
    "                self.addwall(i,j+1)\n",
    "\n",
    "    def border(self,i,j):\n",
    "        if i<0 or j<0 or i>self.m-1 or j>self.n-1:\n",
    "            return False\n",
    "        if self.isInfected[i][j]==-1:\n",
    "            return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containVirus(self, isInfected: List[List[int]]) -> int:\n",
    "        def dfs(i, j):\n",
    "            vis[i][j] = True\n",
    "            areas[-1].append((i, j))\n",
    "            for a, b in [[0, -1], [0, 1], [-1, 0], [1, 0]]:\n",
    "                x, y = i + a, j + b\n",
    "                if 0 <= x < m and 0 <= y < n:\n",
    "                    if isInfected[x][y] == 1 and not vis[x][y]:\n",
    "                        dfs(x, y)\n",
    "                    elif isInfected[x][y] == 0:\n",
    "                        c[-1] += 1\n",
    "                        boundaries[-1].add((x, y))\n",
    "\n",
    "        m, n = len(isInfected), len(isInfected[0])\n",
    "        ans = 0\n",
    "        while 1:\n",
    "            vis = [[False] * n for _ in range(m)]\n",
    "            areas = []\n",
    "            c = []\n",
    "            boundaries = []\n",
    "            for i, row in enumerate(isInfected):\n",
    "                for j, v in enumerate(row):\n",
    "                    # 找到每块连通的病毒区域\n",
    "                    if v == 1 and not vis[i][j]:\n",
    "                        areas.append([])\n",
    "                        boundaries.append(set())\n",
    "                        c.append(0)\n",
    "                        dfs(i, j)\n",
    "            if not areas:\n",
    "                break\n",
    "\n",
    "            # 威胁最大的区域\n",
    "            idx = boundaries.index(max(boundaries, key=len))\n",
    "            # 累加防火墙\n",
    "            ans += c[idx]\n",
    "            for k, area in enumerate(areas):\n",
    "                if k == idx:\n",
    "                    # 此区域已成功堵住\n",
    "                    for i, j in area:\n",
    "                        isInfected[i][j] = -1\n",
    "                else:\n",
    "                    # 向外感染一个区域\n",
    "                    for i, j in area:\n",
    "                        for a, b in [[0, -1], [0, 1], [-1, 0], [1, 0]]:\n",
    "                            x, y = i + a, j + b\n",
    "                            if 0 <= x < m and 0 <= y < n and isInfected[x][y] == 0:\n",
    "                                isInfected[x][y] = 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containVirus(self, isInfected: List[List[int]]) -> int:\n",
    "        def dfs(i, j):\n",
    "            vis[i][j] = True\n",
    "            areas[-1].append((i, j))\n",
    "            for a, b in [[0, -1], [0, 1], [-1, 0], [1, 0]]:\n",
    "                x, y = i + a, j + b\n",
    "                if 0 <= x < m and 0 <= y < n:\n",
    "                    if isInfected[x][y] == 1 and not vis[x][y]:\n",
    "                        dfs(x, y)\n",
    "                    elif isInfected[x][y] == 0:\n",
    "                        c[-1] += 1\n",
    "                        boundaries[-1].add((x, y))\n",
    "\n",
    "        m, n = len(isInfected), len(isInfected[0])\n",
    "        ans = 0\n",
    "        while 1:\n",
    "            vis = [[False] * n for _ in range(m)]\n",
    "            areas = []\n",
    "            c = []\n",
    "            boundaries = []\n",
    "            # enumerate(sequence, [start=0])\n",
    "            # 先返回索引，再返回元素\n",
    "            for i, row in enumerate(isInfected):\n",
    "                for j, v in enumerate(row):\n",
    "                    # 找到每块连通的病毒区域\n",
    "                    if v == 1 and not vis[i][j]:\n",
    "                        areas.append([])\n",
    "                        boundaries.append(set())\n",
    "                        # set() 函数创建一个无序不重复元素集，\n",
    "                        c.append(0)\n",
    "                        dfs(i, j)\n",
    "            if not areas:\n",
    "                break\n",
    "\n",
    "            # 威胁最大的区域\n",
    "            idx = boundaries.index(max(boundaries, key=len))\n",
    "            # 累加防火墙\n",
    "            ans += c[idx]\n",
    "            for k, area in enumerate(areas):\n",
    "                if k == idx:\n",
    "                    # 此区域已成功堵住\n",
    "                    for i, j in area:\n",
    "                        isInfected[i][j] = -1\n",
    "                else:\n",
    "                    # 向外感染一个区域\n",
    "                    for i, j in area:\n",
    "                        for a, b in [[0, -1], [0, 1], [-1, 0], [1, 0]]:\n",
    "                            x, y = i + a, j + b\n",
    "                            if 0 <= x < m and 0 <= y < n and isInfected[x][y] == 0:\n",
    "                                isInfected[x][y] = 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containVirus(self, grid: List[List[int]]) -> int:\n",
    "        row = len(grid)\n",
    "        col = len(grid[0])\n",
    "        dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]\n",
    "\t\t# 找到所有感染区域\n",
    "        def find_all_virus_area(grid):\n",
    "            visited = set()\n",
    "            all_virus_area = []\n",
    "\n",
    "            def helper(i, j, one_virus_area):\n",
    "                visited.add((i, j))\n",
    "                one_virus_area.append((i, j))\n",
    "                for x, y in dirs:\n",
    "                    tmp_i = i + x\n",
    "                    tmp_j = j + y\n",
    "                    if 0 <= tmp_i < row and 0 <= tmp_j < col and (tmp_i, tmp_j) not in visited and grid[tmp_i][\n",
    "                        tmp_j] == 1:\n",
    "                        helper(tmp_i, tmp_j, one_virus_area)\n",
    "\n",
    "            for i in range(row):\n",
    "                for j in range(col):\n",
    "                    one_virus_area = []\n",
    "                    if (i, j) not in visited and grid[i][j] == 1:\n",
    "                        helper(i, j, one_virus_area)\n",
    "                        all_virus_area.append(one_virus_area)\n",
    "            return all_virus_area\n",
    "\t\t# 找出一个区域可能感染的面积\n",
    "        def sprea_area(area):\n",
    "\n",
    "            a = 0\n",
    "            tmp_visited = set()\n",
    "            for i, j in area:\n",
    "                for x, y in dirs:\n",
    "                    tmp_i = i + x\n",
    "                    tmp_j = j + y\n",
    "                    if 0 <= tmp_i < row and 0 <= tmp_j < col \\\n",
    "                            and (tmp_i, tmp_j) not in tmp_visited and grid[tmp_i][tmp_j] == 0:\n",
    "                        tmp_visited.add((tmp_i, tmp_j))\n",
    "                        a += 1\n",
    "            return a\n",
    "\t\t# 找出一个区域需要的隔离带\n",
    "        def circu(area):\n",
    "            cou = 0\n",
    "            # tmp_visited = set()\n",
    "            for i, j in area:\n",
    "                for x, y in dirs:\n",
    "                    tmp_i = i + x\n",
    "                    tmp_j = j + y\n",
    "                    if 0 <= tmp_i < row and 0 <= tmp_j < col and grid[tmp_i][tmp_j] == 0:\n",
    "                        # tmp_visited.add((tmp_i, tmp_j))\n",
    "                        cou += 1\n",
    "            return cou\n",
    "\t\t# 向前感染一格\n",
    "        def sprea(area):\n",
    "            for i, j in area:\n",
    "                for x, y in dirs:\n",
    "                    tmp_i = i + x\n",
    "                    tmp_j = j + y\n",
    "                    if 0 <= tmp_i < row and 0 <= tmp_j < col and grid[tmp_i][tmp_j] == 0:\n",
    "                        grid[tmp_i][tmp_j] = 1\n",
    "\n",
    "        # print(find_all_virus_area(grid))\n",
    "        cur = find_all_virus_area(grid)\n",
    "        res = 0\n",
    "        while cur:\n",
    "            all_virus_area = list(map(sprea_area, cur))\n",
    "            # print(all_virus_area)\n",
    "            # 找出最大感染面积,进行隔离\n",
    "            max_loc = all_virus_area.index(max(all_virus_area))\n",
    "            res += circu(cur[max_loc])\n",
    "            #把已经隔离设置成-1\n",
    "            for i, j in cur[max_loc]:\n",
    "                grid[i][j] = -1\n",
    "            cur.pop(max_loc)\n",
    "            # 感染一格\n",
    "            for area in cur:\n",
    "                sprea(area)\n",
    "            cur = find_all_virus_area(grid)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containVirus(self, grid: List[List[int]]) -> int:\n",
    "        m , n = len(grid) , len(grid[0])\n",
    "        deads = [[False for _ in range(n)] for _ in range(m)]\n",
    "        direction = [[0,1],[1,0],[0,-1],[-1,0]]\n",
    "\n",
    "        def dfs(i,j):\n",
    "            grid[i][j] = 2\n",
    "            x = set()\n",
    "            y = set()\n",
    "            y.add((i,j))\n",
    "            k = 0\n",
    "            for di , dj in direction:\n",
    "                ni , nj = i + di , j + dj\n",
    "                if 0 <= ni < m and 0 <= nj < n and grid[ni][nj] == 1 and not deads[ni][nj]:\n",
    "                    ans = dfs(ni,nj)\n",
    "                    x |= ans[1]\n",
    "                    y |= ans[2]\n",
    "                    k += ans[0]\n",
    "                elif 0 <= ni < m and 0 <= nj < n and grid[ni][nj] == 0:\n",
    "                    x.add((ni,nj))\n",
    "                    k += 1\n",
    "            return k , x , y\n",
    "\n",
    "        def getWall():\n",
    "            q = []\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if grid[i][j] == 1 and not deads[i][j]:\n",
    "                        k , x , y = dfs(i,j)\n",
    "                        heapq.heappush(q,(-len(x),k,x,y))\n",
    "            return q\n",
    "\n",
    "        queue = getWall()\n",
    "        \n",
    "        ans = 0\n",
    "        while queue:\n",
    "            visited = set()\n",
    "            _ , k , _ , y = heapq.heappop(queue)\n",
    "            for i , j in y:\n",
    "                deads[i][j] = True\n",
    "            ans += k\n",
    "            for _ , _ , x , y in queue:\n",
    "                for i , j in x:\n",
    "                    grid[i][j] = 1\n",
    "                for i , j in y:\n",
    "                    grid[i][j] = 1\n",
    "            queue = getWall()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containVirus(self, isInfected: List[List[int]]) -> int:\n",
    "        m, n = len(isInfected), len(isInfected[0])\n",
    "        def dfs(i, j):\n",
    "            if (i, j) in visit:\n",
    "                return \n",
    "            visit.add((i, j))\n",
    "            region[-1].add((i, j))\n",
    "            for d in ((-1, 0), (0, - 1), (1, 0), (0, 1)):\n",
    "                x = i + d[0]\n",
    "                y = j + d[1]\n",
    "                if 0 <= x < m and 0 <= y < n:\n",
    "                    if isInfected[x][y] == 1:\n",
    "                        dfs(x, y)\n",
    "                    elif isInfected[x][y] == 0:\n",
    "                        infect[-1].add((x, y))\n",
    "                        fence[-1] += 1 \n",
    "        res = 0\n",
    "        while True:\n",
    "            region = []\n",
    "            infect = []\n",
    "            fence = []\n",
    "            visit = set()\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if isInfected[i][j] == 1:\n",
    "                        fence.append(0)\n",
    "                        infect.append(set())\n",
    "                        region.append(set())\n",
    "                        dfs(i, j)\n",
    "            if not region:\n",
    "                break \n",
    "            idx = infect.index(max(infect, key = len))\n",
    "            res += fence[idx]\n",
    "            for i in range(len(region)):\n",
    "                if i == idx:\n",
    "                    for r, c in region[i]:\n",
    "                        isInfected[r][c] = - 1\n",
    "                else:\n",
    "                    for r, c in region[i]:\n",
    "                        for d in ((-1, 0), (0, - 1), (1, 0), (0, 1)):\n",
    "                            x = r + d[0]\n",
    "                            y = c + d[1]\n",
    "                            if 0 <= x < m and 0 <= y < n and isInfected[x][y] == 0:\n",
    "                                isInfected[x][y] = 1\n",
    "                                \n",
    "        return res \n",
    "\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containVirus(self, isInfected: List[List[int]]) -> int:\n",
    "        m, n = len(isInfected), len(isInfected[0])\n",
    "        def dfs(i, j):\n",
    "            if (i, j) in visit:\n",
    "                return \n",
    "            visit.add((i, j))\n",
    "            region[-1].add((i, j))\n",
    "            for d in ((-1, 0), (0, - 1), (1, 0), (0, 1)):\n",
    "                x = i + d[0]\n",
    "                y = j + d[1]\n",
    "                if 0 <= x < m and 0 <= y < n:\n",
    "                    if isInfected[x][y] == 1:\n",
    "                        dfs(x, y)\n",
    "                    elif isInfected[x][y] == 0:\n",
    "                        infect[-1].add((x, y))\n",
    "                        fence[-1] += 1 \n",
    "        res = 0\n",
    "        while True:\n",
    "            region = []\n",
    "            infect = []\n",
    "            fence = []\n",
    "            visit = set()\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if isInfected[i][j] == 1:\n",
    "                        fence.append(0)\n",
    "                        infect.append(set())\n",
    "                        region.append(set())\n",
    "                        dfs(i, j)\n",
    "            if not region:\n",
    "                break \n",
    "            idx = infect.index(max(infect, key = len))\n",
    "            res += fence[idx]\n",
    "            for i in range(len(region)):\n",
    "                if i == idx:\n",
    "                    for r, c in region[i]:\n",
    "                        isInfected[r][c] = - 1\n",
    "                else:\n",
    "                    for r, c in region[i]:\n",
    "                        for d in ((-1, 0), (0, - 1), (1, 0), (0, 1)):\n",
    "                            x = r + d[0]\n",
    "                            y = c + d[1]\n",
    "                            if 0 <= x < m and 0 <= y < n and isInfected[x][y] == 0:\n",
    "                                isInfected[x][y] = 1\n",
    "                                \n",
    "        return res \n",
    "\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containVirus(self, isInfected: List[List[int]]) -> int:\n",
    "\n",
    "        # 每个循环对感染区域进行BFS，获取当前感染联通区域、能够感染的数量、添加挡板数量（只要感染节点能够渗透到未感染区域则需要加一个挡板）\n",
    "        # 对能够感染周围数量最大的联通区域增加挡板（将此联通区域的点标记为2），对其它区域能够感染的周围进行感染\n",
    "        # 进入下一个循环，直到没有感染的点\n",
    "        m, n, ans = len(isInfected), len(isInfected[0]), 0\n",
    "        # 0未感染，1感染，2已隔离, 3周围被感染\n",
    "        def checkIsInfected(isInfected):\n",
    "            for r in range(m):\n",
    "                for c in range(n):\n",
    "                    if isInfected[r][c] == 1:\n",
    "                        return True\n",
    "            return False\n",
    "        def bfs(isInfected, r, c, visited):\n",
    "            area = [[0] * n for _ in range(m)] # 当前感染联通区域\n",
    "            queue = deque([[r, c]])\n",
    "            cnt = 0\n",
    "            baffle = 0\n",
    "            area[r][c] = 1\n",
    "            visited[r][c] = True\n",
    "            while queue:\n",
    "                curR, curC = queue.popleft()\n",
    "                # 能否感染周围\n",
    "                for dr, dc in [[-1, 0], [0, -1], [1, 0], [0, 1]]:\n",
    "                    ar, ac = curR + dr, curC + dc\n",
    "                    if 0 <= ar < m and 0 <= ac < n and isInfected[ar][ac] == 0:\n",
    "                        if area[ar][ac] != 3:\n",
    "                            cnt += 1\n",
    "                            area[ar][ac] = 3\n",
    "                        baffle += 1\n",
    "                for diffR, diffC in [[-1, 0], [0, -1], [1, 0], [0, 1]]:\n",
    "                    nextR, nextC = curR + diffR, curC + diffC\n",
    "                    if 0 <= nextR < m and 0 <= nextC < n and area[nextR][nextC] == 0 and isInfected[nextR][nextC] == 1:\n",
    "                        area[nextR][nextC] = 1\n",
    "                        visited[nextR][nextC] = True\n",
    "                        queue.append([nextR, nextC])\n",
    "                        \n",
    "            return baffle, cnt, area[::][::]\n",
    "\n",
    "        while checkIsInfected(isInfected):\n",
    "            maxEffectCnt = 0 # 当前最大威胁\n",
    "            memo = defaultdict(list)\n",
    "            visited = [[False] * n for _ in range(m)]\n",
    "            for r in range(m):\n",
    "                for c in range(n):\n",
    "                    if isInfected[r][c] == 1 and not visited[r][c]:\n",
    "                        baffle, curEffectCnt, curEffectArea = bfs(isInfected, r, c, visited)\n",
    "                        memo[curEffectCnt].append([baffle, curEffectArea[::][::]])\n",
    "                        if curEffectCnt > maxEffectCnt:\n",
    "                            maxEffectCnt = curEffectCnt\n",
    "            for cnt, areas in memo.items():\n",
    "                for baffle, area in areas:\n",
    "                    if cnt == maxEffectCnt:\n",
    "                        ans += baffle\n",
    "                    for r in range(m):\n",
    "                        for c in range(n):\n",
    "                            if cnt == maxEffectCnt:\n",
    "                                if area[r][c] == 1:\n",
    "                                    isInfected[r][c] = 2\n",
    "                            else:\n",
    "                                if area[r][c] == 3:\n",
    "                                    isInfected[r][c] = 1 # 感染\n",
    "            # print(isInfected)\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
